## 选择基站候选点
#   原理： 1.找出已部署基站的边缘，所有基站的边缘组合在一起当做一个大边缘（也可能是多个，邻接边缘可以合在一起）
#          2.从边缘一端开始寻找距离起点（端点）为中继距离的边缘点，一直寻找到另一端点并计数为n，则所需部署的新基站个数为n
#          3.根据新一轮基站数n，将大边缘进行等分，等分点便是基站候选点
#   参数： BS表示当前所有基站 BS_last表示上一轮基站的第一个 BS_current表示上一轮基站的最后一个 robot表示所有机器人对象  C表示当前的区域覆盖情况
#          id表示中继距离  dL表示网格距离
#   返回值：当前所有的基站候选点   新一层基站（按照角度排序的）   新一层基站对应的边缘点

import math
import numpy


def chose_bs_point(BS, BS_last, BS_current, C, id, dL):
    Points = []
    BS_new_order = []
    BS_new_edgepoints = []
    # 原点基站寻找基站候选点
    if BS[BS_current, 1] == 0:
        # 为了提高通信链路的鲁棒性，原点基站默认选择两个候选基站
        Points = id * [[math.cos(math.pi * 30 / 180), math.cos(math.pi * 60 / 180)], [math.sin(math.pi * 30 / 180), math.sin(math.pi * 60 / 180)]] / dL
        BS_new_order = []
        BS_new_edgepoints = []
    # 非原点找基站候选点
    else:
        # ======= 1.求出边缘点坐标 ======= #
        array = numpy.argwhere(C == 49)
        points = []  # 存放排过序的边缘点

        # ======= 2.修正边缘点列表（不能直接用，因为点的顺序问题） ======= #
        # ======= 通过上一轮增加的基站 and 边缘点，判断边缘点与基站的匹配，根据基站与原点的角度顺序对边缘点进行排序，得到有序的边缘点 ======= #
        # 2.1新增加的基站列表
        BS_new = BS[BS_last:BS_current] / dL
        # 2.2 把基站按照角度排序
        BS_th = math.atan2(0-BS_new[:,2], 0-BS_new[:,1])
        BS_th = numpy.hstack((BS_th, BS_new))
        BS_th = BS_th[numpy.lexsort(BS_th[:, ::-1].T)] # 按照第一列基站相对于原点的角度升序排序
        BS_new = BS_th[:, 1:4]  # 取出按照角度排序后的基站列表

        BS_new_order = []
        BS_new_edgepoints = []
        # 2.3 循环新基站
        for i in range(len(BS_th)):
            # 2.3.1 求出与所有边缘点的距离，找出距离等于中继距离的边缘点
            dis = math.sqrt(numpy.square(BS_new[i, 1]-array[:, 0])+numpy.square(BS_new[i, 2]-array[:, 1]))
            poin_new = numpy.argwhere(abs(dis - round(id / dL)) < 2.4)
            if len(poin_new) > 0:
                # 2.3.2 求出基站与自己的边缘点的角度
                poin_th = math.atan2(poin_new[:, 3]-BS_new[i,2], poin_new[:, 2]-BS_new[i,1])
                # 角度与边缘点坐标合并
                poin_th = numpy.insert(poin_th, len(poin_th), poin_new, axis=0)
                # 按照角度升序排序
                poin_th = poin_th[numpy.lexsort(poin_th[:, ::-1].T)] # 按照第一行升序排序
                # 取出按照角度排序后的边缘点
                poin_new = poin_th[:][1:2]
                # 添加到总的边缘点列表中
                points = numpy.insert(points, len(points), poin_new, axis=0)
                # 添加到新一层基站对应的边缘点列表中
                BS_new_edgepoints = numpy.insert(BS_new_edgepoints, len(BS_new_edgepoints), poin_new * dL, axis=0)
                BS_new_order = numpy.insert(BS_new_order, len(BS_new_order), BS_new[i][:], axis=0)

        BS_new = BS_new * dL;

        # ======= 3.将边缘点列表分段 ======= #
        # 删除相同的点（行）
        points = numpy.array(list(set([tuple(t) for t in points])))
        # 定义边缘点元组
        edge_points = []  # 定义一个存放边缘点的列表
        # 保留第一个点
        p = points[0][:]
        # 删除第一个点
        points = points[1:len(points)]
        # 临时边缘点有序列表（保存完一段边缘点后，加入edge_points列表）
        temp_edge = []
        # 将其加入边缘点列表
        temp_edge.append(p)
        # 循环边缘点列表，找出距离最小的临近点
        while len(points) > 0:
            min_value = math.sqrt((p[0, 0] - points[0, 0])**2 + (p[0, 1] - points[0, 1])**2)
            # 判断两个相邻的边缘点是否属于同一段
            if min_value <= math.sqrt(2):   # 属于同一段
                temp_edge.append(points[0, :])  # 将其加入边缘点列表
                p = points[0, :]  # 保留新加入的边缘点
                points = points[1:len(points)]  # 继续删除第一个点
            else:
                edge_points.append(temp_edge)  # 将前面的一段边缘点加入边缘点列表
                temp_edge = []  # 清空临时边缘点有序列表
                p = points[0, :]   # 更新下一段的初始点
                points = points[1:len(points)]  # 删除该点

        edge_points.append(temp_edge)  # 将前面的一段边缘点加入边缘点列表

        # ======= 4.将边缘点等距均分 ======= #
        # 4.遍历每一段边缘点（此时的边缘点是有序的）
        for i in range(len(edge_points)):
            edge_point = edge_points[i]  # 单独取出第 i 段边缘点
            bs_candidate = []  # 存放候选基站点的行号（在edge_point中的行号）
            # ======= 4.1 对于每一段边缘点求出应部署的基站数 ======= #
            bs_num = 0
            begin_point = edge_point[0]  # 起始边缘点
            for j in range(1, len(edge_point)):
                if 2 > abs(math.sqrt((begin_point[0,0]-edge_point[j, 0])**2-(begin_point[0,1]-edge_point[j, 1])**2)-round(id/dL)):
                    bs_num = bs_num + 1     # 基站点个数加一
                    bs_candidate.append(j)  # 添加候选基站点（在edge_point中的行号）
                    if j == len(edge_point):
                        break
                    begin_point = edge_point[j]  # 更新起始边缘点
            if bs_num == 0:
                bs_num = 1

            # ======= 4.2 对于每一段边缘点进行等距基站部署，确定基站位置 ======= #
            change_flag = 1    # 调整变量，当这个值为时，代表基站候选点调整完毕
            # 4.2.1 找出中间点的下标
            bs_candidate.insert(0, 1)  # 把两端的下标也加入
            bs_candidate.append(len(edge_point))
            while change_flag == 1:
                change_flag = 0
                # 从第二个开始，循环到倒数第二个
                for j in range(1, len(bs_candidate)-1):
                    # 寻找中间的边缘点
                    mid_index = search_mid(edge_point[bs_candidate[j-1]: bs_candidate[j+1], :], bs_candidate[j-1])
                    if mid_index != bs_candidate[j]:
                        change_flag = 1  # 表明此次寻找到新的基站位置
                        bs_candidate[j] = mid_index  # 更新基站候选点的行号
            for j in range(1, len(bs_candidate)-1):
                Points.append(edge_point[j][:])  # 得到最终的等距基站候选点

# 找出位于中间的边缘点
def search_mid(points, front):
    dis = []
    # 循环求出每个点到两端的距离差值
    for i in range(1, len(points)-1):
        dis_front = math.sqrt((points[0][0]-points[i][0])**2 + (points[0][1]-points[i][1])**2)
        dis_after = math.sqrt((points[-1][0]-points[i][0])**2 + (points[-1][1]-points[i][1])**2)
        dis.append(abs(dis_front - dis_after))

    min_value = min(dis)
    index = dis.index(min_value)
    index = index + front
    return index
